package com.fftf.algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author qiancheng 18638109122@163.com
 * @desc
 * @create 2021/2/4 15:29
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {3, 2, 5, 4, 7, 8, 9, 10};
        doubleSideQuickSort(0,arr.length-1,arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * @param left  left
     * @param right right
     * @param arr   数组
     */
    public static void doubleSideQuickSort(int left, int right, int[] arr) {
        if (left > right) {
            return;
        }

        //以首元素为基准值
        int base = arr[left];
        //定义左指针
        int i = left;
        //定义右指针
        int j = right;

        //右指针-》左  左指针-》右
        while (i != j) {
            //循环找出第一个比基准值小的元素
            while (arr[j] >= base && i < j) {
                //指针左移
                j--;
            }
            //循环找出第一个比基准值大的元素
            while (arr[i] <= base && i < j) {
                //指针左移
                i++;
            }

            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }

        //退出循环i=j 此时交换i 和 j的对应的元素的值
        arr[left]=arr[i];
        arr[i]=base;

        doubleSideQuickSort(left,i-1, arr);
        doubleSideQuickSort(i+1,right, arr);
    }
}
